#!/usr/bin/env python

from collections import deque

class BinaryTreeNode:
    def __init__(self, item = None, lchild = None, rchild = None, p = None):
        self._item = item
        self._lchild = lchild
        self._rchild = rchild
        self._parent = p

    @property
    def item(self):
        return self._item

    @item.setter
    def item(self, val):
        self._item = val

    @property
    def lchild(self):
        return self._lchild

    @lchild.setter
    def lchild(self, child):
        self._lchild = child

    @property
    def rchild(self):
        return self._rchild

    @rchild.setter
    def rchild(self, child):
        self._rchild = child

    @property
    def parent(self):
        return self._parent

    @parent.setter
    def parent(self, p):
        self._parent = p

    def is_leaf(self):
        return self._lchild is None and self._rchild is None

    def __str__(self):
        return str(self.item)


class BinarySearchTree:
    def __init__(self):
        self._root = None
        self._size = 0

    def is_empty(self):
        return self._size == 0

    def size(self):
        return self._size

    def __len__(self):
        return self.size()

    def insert(self, item):
        node = BinaryTreeNode(item)
        cur = self._root
        parent = None

        if cur is None:
            self._root = node
            return

        while cur is not None:
            parent = cur
            if cur.item > item:
                cur = cur.lchild
            else:
                cur = cur.rchild

        if node.item > parent.item:
            parent.rchild = node
        else:
            parent.lchild = node

        node.parent = parent
        self._size += 1

    def search(self, item):
        cur = self._root

        while cur is not None:
            if cur.item == item:
                return cur
            else:
                cur = cur.lchild if cur.item > item else cur.rchild
        
        return None

    def delete(self, item):
        node = self.search(item)
        if node is None:
            return

        if node.is_leaf():
            if node.parent.item > node.item:
                node.parent.lchild = None
            else:
                node.parent.rchild = None

        elif node.lchild is None and node.rchild is not None:
            node.rchild.parent = node.parent
            if node.parent.item > node.item:
                node.parent.lchild = node.rchild
            else:
                node.parent.rchild = node.rchild

        elif node.lchild is not None and node.rchild is None:
            node.lchild.parent = node.parent
            if node.parent.item > node.item:
                node.parent.lchild = node.lchild
            else:
                node.parent.rchild = node.lchild
        else:
            max_node = self.get_max(node.lchild)
            self.delete(max_node.item)
            node.item = max_node.item

        self._size -= 1

    def get_max(self, node = None):
        if node is None:
            cur = self._root
        else:
            cur = node

        if cur is None:
            return None

        while cur.rchild is not None:
            cur = cur.rchild

        return cur


    def get_min(self, node = None):
        if node is None:
            cur = self._root
        else:
            cur = node

        if cur is None:
            return None

        while cur.lchild is not None:
            cur = cur.lchild

        return cur

    def __str__(self):
        def backtacking(node, ans):
            if node is None:
                return 
            else:
                backtacking(node.lchild, ans)
                ans.append(node.item)
                backtacking(node.rchild, ans)
        
        ans = []
        backtacking(self._root, ans)
        return str(ans)

    @staticmethod
    def build_binary_search_tree(items):
        t = BinarySearchTree()
        for item in items:
            t.insert(item)
        
        return t

    def level_order_transveral(self):
        queue = deque()
        queue.append(self._root)
        ans = []

        while len(queue) > 0:
            node = queue.popleft()
            ans.append(node.item)
            
            if node.lchild is not None:
                queue.append(node.lchild)
            
            if node.rchild is not None:
                queue.append(node.rchild)

        return ans    

if __name__ == "__main__":
    t = BinarySearchTree.build_binary_search_tree([1, 2, 3, 4, 10, 30, 80, 72])
    print(t)
    
    print(t.search(80))
    print(t.get_max())
    print(t.get_min())
    print(t.size(), len(t))
    t.delete(4)
    print(t)
    print(t.search(30))
    print(t.size(), len(t))
    print(t.level_order_transveral())